\documentclass{ctexart}

\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{subfigure}

\title{Bellman-Ford 算法的实现}



\author{赖心怡 \\  医学实验班(临床医学八年制) 3210100987}

\begin{document}

\maketitle

\section{项目设计思路}

Bellman-ford 算法是一种比dijkstra算法更具普遍性的算法，因为它对边没有要求，可以处理负权边与负权回路。缺点是时间复杂度过高，每一次运行的时间复杂度高达 $O(VE)$, $V$ 为顶点数，$E$ 为边数, 在稠密图的条件下, $E = V ^ {2}$, 时间复杂度可达 $O(V ^ {3})$。其主要思想：对所有的边进行n-1轮松弛操作，因为在一个含有n个顶点的图中，任意两点之间的最短路径最多包含n-1边。换句话说，第1轮在对所有的边进行松弛后，得到的是源点最多经过一条边到达其他顶点的最短距离；第2轮在对所有的边进行松弛后，得到的是源点最多经过两条边到达其他顶点的最短距离......由归纳法可知,最终可得源点到各顶点的最短路径.

本项目在上一次作业的基础上,通过 \verb|void Bellman_Ford()| 函数实现了基于邻接矩阵存储的图的 Bellman-Ford 算法.其核心代码如下:
\begin{verbatim}
for(int m = 1; m < n; m ++){//m:经过顶点的个数
                for(int i = 0; i < n; i ++){//i:起点
                        for(int j = 0; j < n; j ++){//j:终点
                                for(int k = 0; k < n; k ++){//k:过渡点
                                        if(edge[k][j] != 0){
                                                if(d[i][j] > d[i][k] + edge[k][j]){
                                                        d[i][j] = d[i][k] + edge[k][j];
						}
						}
						}
						}
						}
						}
\end{verbatim}

\section{测试流程说明}

(1)测试用户输入不正确时出现的异常处理,例如建立顶点数为5, 边数唯一的图, 如 Figure 1 所示:
\begin{figure}[htbp]
        \centering
	\includegraphics{figure1.png}
	\caption{用户输入不正确}
	\label{Figure 1}
\end{figure}

(2)测试 Bellman-Ford 算法能正确实现, 如 Figure 2 所示:
\begin{figure}[htbp]
        \centering
        \includegraphics{figure2.png}
        \caption{测试算法正确性}
        \label{Figure 2}
\end{figure}

(3)通过改变图的顶点数 $n$, 测试算法的时间效率, 可证明算法整体的时间复杂度为 $O(n ^ {4}) $, 具体测试结果如 Figure 3 所示:
\begin{figure}[htbp]
        \centering
        \includegraphics{figure3.png}
        \caption{测试算法正确性}
        \label{Figure 3}
\end{figure}

(4)内存泄漏检查结果如下:
\begin{verbatim}
==3092== 
==3092== HEAP SUMMARY:
==3092==     in use at exit: 0 bytes in 0 blocks
==3092==   total heap usage: 3 allocs, 3 frees, 74,752 bytes allocated
==3092== 
==3092== All heap blocks were freed -- no leaks are possible
==3092== 
==3092== For counts of detected and suppressed errors, rerun with: -v
==3092== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
\end{verbatim}

(5)一些问题:当 $n = 1000$ 时可以从返回的时间上看出程序存在问题, 多次运行后报错内存泄漏,但内存泄漏检查无误,可能是因为可提供的边数较少, 存储空间有较大的浪费造成问题?
\end{document}

